#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define ElemType int

typedef struct{
	ElemType *data;
	int length;
	int maxsize;
}SqList;

SqList* initList(int maxsize); // 初始化顺序表
void messageList(SqList* L); // 打印顺序表的信息和数据
int getLength(SqList* L); // 获取顺序表长度
int locateElem(SqList* L, ElemType e); //获取指定元素的位置
ElemType getElem(SqList* L, int i); // 通过指定位置获取对应的元素
bool listInsert(SqList* L, int i, ElemType e); // 在指定位置插入元素
bool listAppend(SqList* L, ElemType e); // 在顺序表的最后插入元素
bool listPrepend(SqList* L, ElemType e); // 在顺序表的开始插入元素
bool isEmpty(SqList* L); // 判断链表是否为空
void release(SqList* L); // 销毁链表
void clear(SqList* L); // 将线性表清空
bool delElem(SqList* L, int pos); // 删除顺序表指定位置的元素

int main()
{
	SqList* L = initList(11);
	for(int i = 0; i < 10; i++)
	{
		// listAppend(L, i*2);
		listPrepend(L, i*2);
	}
	// listInsert(L, 2, 20);
	// printf("%d\n", getElem(L, 2));
	// printf("%d\n", getLength(L));
	// printf("%d\n", locateElem(L, 16));
	// printf("%d\n",isEmpty(L));
	// messageList(L);
	// clear(L);
	// release(L);
	messageList(L);
	delElem(L,11);
	messageList(L);
	return 0;
}

SqList* initList(int maxsize)
{
	SqList* L = NULL;
	L = (SqList *)malloc(sizeof(SqList));
	if(L == NULL)
	{
		printf("表头创建失败!\n");
		return NULL;
	}
	L->data = (ElemType*)malloc(sizeof(ElemType)*maxsize);
	if(L == NULL)
	{
		printf("数据节点分配空间失败!\n");
		return NULL;
	}
	L->length = 0;
	L->maxsize = maxsize;
	return L;
}

void messageList(SqList* L)
{
	if ( L != NULL)
	{
		printf("data length: %d\n", L->length);
		printf("maxsize: %d\n", L->maxsize);
		printf("data:\n");
		for(int i=0; i<L->length;i++)
		{
			printf("%d ", L->data[i]);
			if ((i+1) % 5 == 0)
			{
				printf("\n");
			}
		}
	}	
}


int getLength(SqList* L)
{
	return L->length;
}


int locateElem(SqList* L, ElemType e)
{
	for(int i = 0; i < L->length; i++)
	{
		if(L->data[i] == e)
		{
			return i+1;
		}
	}
	return -1;
}


ElemType getElem(SqList* L, int i)
{
	// 判断位置获取元素的位置是否合理
	if ( i < 1 || i > L->length+1)
	{
		printf("获取元素的位置不合理\n");
		return NULL;
	}
	return L->data[i-1];
}


bool listInsert(SqList* L, int pos, ElemType e)
{

	// 判断插入的位置是否合理
	if ( pos < 1 || pos > L->length + 1)
	{
		printf("插入的位置不合理!");
		return false;
	}
	
	// 判断是否还有空闲的位置
	if ( L->length >= L->maxsize)
	{
		printf("顺序表已满!\n");
		return false;
	}
	
	// 将插入位置之后的元素后移
	for(int i = L->length; i >= pos; i--)
	{
		L->data[i] = L->data[i-1];
	}
	
	L->data[pos-1] = e;
	L->length++;
	
	return true;
}


bool listAppend(SqList* L, ElemType e)
{
	
	return listInsert(L, L->length+1, e);
}

bool listPrepend(SqList* L, ElemType e)
{
	return listInsert(L, 1, e);
}


bool isEmpty(SqList* L)
{
	return L->length == 0;
}

void release(SqList* L)
{
	if( L != NULL)
	{
		
		free(L->data);
		free(L);
	}
}


void clear(SqList* L)
{
	L->length = 0;
}


bool delElem(SqList* L, int pos)
{
	if(pos < 1 || pos > L->length)
	{
		printf("删除的位置不正确\n");
		return false;
	}
	for(int i=pos; i < L->length; i++)
	{
		L->data[i-1] = L->data[i];
	}
	L->length--;
	return true;
}
